/**
    ******************************************************************************
    * @file    binHeap.c
    * @author  debian
    * @version V1.0.0
    * @date    2020-01-19
    * @brief   二叉堆
    ******************************************************************************
    * @attention
    *
    *
    ******************************************************************************
    */ 

/* Includes ------------------------------------------------------------------*/
#include "binHeap.h"
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <assert.h>

/** @addtogroup DataStruct_Driver
    * @{
    */

/** @addtogroup binHeap
    * @{
    */

/* Private typedef -----------------------------------------------------------*/

/* Private define ------------------------------------------------------------*/

/* Private macro -------------------------------------------------------------*/

/* Private variables ---------------------------------------------------------*/

/* Private function prototypes -----------------------------------------------*/

/* Private functions ---------------------------------------------------------*/


/** @defgroup binHeap_Exported_Functions binHeap Exported Functions
    * @{
    */

/** @defgroup binHeap_Exported_Functions_Group1 Initialization and deinitialization functions
    *  @brief    Initialization and Configuration functions
    *
@verbatim    
    ===============================================================================
                ##### Initialization and deinitialization functions #####
    ===============================================================================
    [..]
        This section provides functions allowing to initialize and de-initialize the binHeap
        to be ready for use.
 
@endverbatim
    * @{
    */ 

/**
    * @brief  创建binHeap对象
    * @param  
    * @retval 
    */ 
    struct binHeap *binHeap_creat(int size)
    {
		struct binHeap *heap = (struct binHeap *)malloc(sizeof(struct binHeap));
		assert(heap);

		Elemtype *data = (Elemtype *)malloc(sizeof(Elemtype) *size);
		assert(data);

		heap->len = 0;
		heap->data = data;
		heap->size = size;
	
        return heap;
    }

/**
    * @brief  销毁binHeap对象
    * @param  
    * @retval 
    */ 
    int binHeap_destroy(struct binHeap *heap)
    {
		assert(heap);

		if(heap->data)
			free(heap->data);

		if(heap)
			free(heap);
		
		return 0;
    }
    
/**
    * @}
    */

/** @defgroup binHeap_Exported_Functions_Group2 operation functions 
    *  @brief   operation functions
    *
@verbatim   
    ===============================================================================
                        ##### operation functions #####
    ===============================================================================
    [..]
        This subsection provides a set of functions allowing to manage the binHeap.

@endverbatim
    * @{
    */

/**
	* @brief  最小堆下沉
	* @param  
	* @retval 
	*/ 
	static int minHeap_downAdjust(struct binHeap *heap)
	{
		//调整的时候，就是不断的和孩子结点比较，然后获取到那个孩子结点的值比父节点的小，替换父节点

		int parent = 0;
		int left_child = 2 * parent + 1;
		int right_child = 2 * parent + 2;
		int child = left_child;

		Elemtype temp = heap->data[parent];
		
		while(parent < heap->len)
		{
			//如果存在右孩子，并且右孩子小于左孩子，
			if(right_child < heap->len && heap->data[right_child] < heap->data[left_child]) {
				child = right_child;  //父节点要跟右孩子比较
			}

			//判断父节点如果小于等于最小孩子结点，就不用移动
			if(temp <= heap->data[child])
				break;

			//这个需要下沉
			heap->data[parent] = heap->data[child];
			parent = child;
			left_child = parent * 2 + 1; 
			right_child = parent * 2 + 2; 
			child = left_child; 
		}

		heap->data[parent] = temp;
		return 0;
	}



/**
	* @brief  最小堆上浮
	* @param  
	* @retval 
	*/ 
	static int minHeap_upAdjust(struct binHeap *heap)
    {
		//调整的时候，就是不断的和父节点比较，然后判断是否替换父节点

		int child = heap->len - 1; 
		int parent = (child - 1)/2;
		Elemtype temp = heap->data[heap->len-1];

		//开始循环比较
		while(child)
		{
			
			//跟第一个父节点比较
			if(temp < heap->data[parent]){
				//上浮
				heap->data[child] = heap->data[parent];
				child = parent;
				parent = (child - 1)/2;  //找父节点
			}
			
		}

		heap->data[child] = temp;
		return 0;
	}

/**
    * @brief  构建二叉堆
    * @param  
    * @retval 
    */ 
	int minHeap_build(Elemtype data[], int data_len)
	{
		//不写了


		return 0;
	}

/**
    * @brief  二叉堆插入
    * @param  
    * @retval 
    */ 
	int binHeap_insert(struct binHeap *heap, Elemtype data)
	{
		//判断数据元素是否已经超出
		if(heap->size <= heap->len + 1)   //可以实现扩容
			return -1;

		heap->data[heap->len] = data;
		heap->len++;

		minHeap_upAdjust(heap);
	
		return 0;
	}


/**
	* @brief  二叉堆删除
	* @param  
	* @retval 
	*/ 
	int binHeap_delete(struct binHeap *heap)
	{
		//判断数据元素是否已经超出
		if(heap->size <= 0)   //可以实现扩容
			return -1;

		int head = heap->data[0];

		heap->data[0] = heap->data[heap->len-1];
		heap->len--;

		minHeap_downAdjust(heap);
	
		return head;
	}



	#if 1


	int main()
	{
		

		return 0;
	}


	#endif

    /**
    * @}
    */


/**
    * @}
    */

/**
    * @}
    */

/**
    * @}
    */

/************************ (C) 2020 HOME 深圳龙华 *****END OF FILE****/

